联合省选2020 乱写
冰火战士
就是求一个 $lim$ 使得 $\min( \sum\limits_{b_i \leq lim} a_i, \sum\limits_{d_i \geq lim} c_i )$ 最大。$X$ 型函数求交点问题，考虑二分，但线段树上二分太慢了……
卡常神器：BIT + 倍增。二分找到第一个冰系前缀和不小于火系后缀和的位置，稍微移项得「两种前缀和之和不小于火系全和」。
组合数问题
Trick：$\binom{n}{k} k^{\underline{m}} = \binom{n - m}{k - m} n^{\underline{m}}$（易证）
把 $f(k)$ 变成下降幂形式 $\sum\limits_{i = 0}^m b_i k^{\underline{i}}$，再把 $\binom{n}{k} k^{\underline{i}}$ 变成 $\binom{n - i}{k - i} n^{\underline{i}}$，变换求和符号，上二项式定理就做完了。
$Code$ 模数非质啊啊啊
信号传递
状压 dp, $f_S = \min_x( f_{S - x} + |S| ( \sum\limits_{y \in S - x} (K c_{x, y} + c_{y, x}) + \sum\limits_{y \notin S - x} (K * c_{y, x} - c_{x, y}) ) )$。复杂度 $O(2^m m^2)$，空间 $O(2^m m)$，都不行。
考虑把 $|S| $ 后面那坨括号设为 $g_{S, x}$，后面那个计算 $y \notin S - x$ 的用容斥，即最开始先算好全集，到时候抠掉 $y \in S - x$ 的错误贡献就好了。则 $g_{S, x} = g_{S - x, x} + (K c_{x, y} + c_{y, x} ) - ( K * c_{y, x} - c_{x, y} )$，$y$ 取 $lowbit(S - x)$ 这样转移就是 $O(1)$ 的了。
空间怎么搞呢？注意到每个 $g_{S - x}$ 在给 $g_{S}$ 转移完后就失去价值了，考虑回收。具体用 queue 实现。
树
逆建 01 Trie（从低位到高位插入），维护 $v_{a_i} + d(x, a_i)$ 的集合，这样每次 $+ 1$ 就是 $0$ 变 $1$ 并返回，或者 $1$ 变 $0$ 并继续递归。直接交换儿子并递归到改后的 $0$ 子树里去继续修改就好了。记录每位 $1$ 的奇偶。单次 $logV$，总的就是 $nlogV$。
还剩两道毒瘤题。。。/kk
作业题
反演一波，根据 $n = \sum\limits_{d \mid n}$ 可得 $ans = \sum\limits_{d = 1}^{V} \varphi(d) \sum\limits_{d \mid w_{e_i}} ( \sum\limits_{i = 1}^{n - 1} w_{e_i} )$
trick: 矩阵树求边权和，边权为 $1 + w_i x$，答案为行列式的一次项系数。所以行列式只需在模 $x^2$ 意义下计算，维护 $x^0$ 和 $x^1$ 项即可。拉插就算了吧
复杂度 $O(Vn^3)$，会 T。玄学优化：边少于 $n - 1$ 就跳过。于是非常跑不满。
行列式除法：$(ax + b)^{-1} \equiv -\frac{a}{b^2} + \frac{1}{b} \pmod{x^2}$；寻找当前位置非零行，若存在常数项非零则直接选那个，否则常数项都为零，选一次项系数非零的。代码超好写。
魔法商店
终于……要开始贺了么…… 拟阵？保序回归？蒟蒻全都不会哒！
异或相关啊。任何一个 $c_i$, $i \notin A$ 都可以被 $A$ 的一个子集异或出来，否则 $A$ 就不是最大的了。对于 $k \notin A$，设 $s_k$ 表示 $A$ 中异或出 $c_k$ 的集合（这个可以线性基 + bitset/ll数组 得到）。$A$ 价格总和最小的充要条件是 $v_k \geq \max\limits_{i \in s_k}(v_i)$。对 $B$ 也可以得到一些 $\geq$ 关系。把这些关系建成边，问题转化为「在一个 DAG 上，把第 $i$ 个点点权修改为 $x$ 的代价是 $(x - v_i)^2$，要求每个点点权大于等于其所有后继」，即一个经典的保序回归问题。
感性理解一下保序回归吧。。整体二分，如果一个值在当前情况中取 $mid$ 最优，那么在最终答案其应取 $\leq mid$，否则应取 $> mid$。
强制每个点先为 $mid + 1$，那么选一个点为 $mid$ 相当于强制其后继也为 $mid$，边权反一下（准确的说是连边方向换一下，原来和 $S$ 连的现在和 $T$ 连）做最大权闭合子图问题。
复杂度 $O(n^2 nB logV)$，$B$ 这里是 $64$ 甭慌人家稳着呢
丁香之路
挺妙的…… 这种结论题，考思维模式的，唉，我就不行。
答案一定是一条欧拉回路，这个欧拉回路由这 m 条必走边和一些你添加的凑度数的边组成。
具体来说先给起始点连边，奇度点肯定是两两配对，不会带上偶度点的，那必然是相邻的两个奇度点配对。但是当前可能有若干个连通块，没关系，求 MST 即可，代价是 MST 边权和两倍。